﻿using Assets.Scripts.Bvh.Common;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Assets.Scripts.Bvh.Cpu
{
    class CpuSorter
    {
        // 快速排序的主方法
        public static void QuickSort(List<RadixTreeNode> leafNodes, int left, int right)
        {
            if (left < right)
            {
                // 找到分区点
                int partitionIndex = Partition(leafNodes, left, right);

                // 递归地对左子数组进行快速排序
                QuickSort(leafNodes, left, partitionIndex - 1);

                // 递归地对右子数组进行快速排序
                QuickSort(leafNodes, partitionIndex + 1, right);
            }
        }
        // 快速排序的分区方法，用于将数组分割成两个子数组
        private static int Partition(List<RadixTreeNode> leafNodes, int left, int right)
        {
            // 选择最右边的元素作为基准
            int pivot = leafNodes[right].mortonCode;
            int i = left - 1; // i 是较小元素的索引

            for (int j = left; j < right; j++)
            {
                // 如果当前元素小于或等于基准
                if (leafNodes[j].mortonCode <= pivot)
                {
                    i++; // 增加较小元素的索引

                    // 交换 array[i] 和 array[j]
                    Swap(leafNodes, i, j);
                }
            }

            // 将基准元素移动到它的最终位置
            Swap(leafNodes, i + 1, right);
            return i + 1; // 返回分区点
        }
        // 交换数组中两个元素的方法
        private static void Swap(List<RadixTreeNode> leafNodes, int i, int j)
        {
            var temp = leafNodes[i];
            leafNodes[i] = leafNodes[j];
            leafNodes[j] = temp;
        }
    }
}
